#include <stdlib.h>
#include "PQ.h"

//参考程序4.5(栈的链表实现)
typedef struct PQnode* link;

struct PQnode {
    Item item;
    link next;
};

link head;

void PQinit(int maxN){
    head = NULL;
}

int PQempty(){
    return head == NULL;
}

void PQinsert(Item v){
    link t = malloc(sizeof(*t));
    t->item = v;
    t->next = head;
    head = t;
}

Item PQdelmax(){
    // 需要遍历链表找到最大项和其前一个节点
    link current = head;
    link maxNode = head;
    link prevNode = NULL; // 用于跟踪当前节点的前一个节点
    link prevMaxNode = NULL; // 用于跟踪最大项节点的前一个节点
    while (current != NULL) {
        if (less(maxNode->item, current->item)) {
            maxNode = current;
            prevMaxNode = prevNode;
        }
        prevNode = current;
        current = current->next;
    }

    Item maxItem = maxNode->item;

    if (maxNode == head) {
        head = maxNode->next;
    }else {
        prevMaxNode->next = maxNode->next;
    }

    free(maxNode);
    return maxItem;
}
